package org.hot100.h215;

import java.util.Arrays;

/**
 * @Author: wjy
 * @Date: 2022/2/10 11:08
 */
public class Solution {

    public static void main(String[] args) {

        int[] ints = {3, 2, 1, 5, 6, 4};
        //int[] ints = {3,2,3,1,2,4,5,5,6,7,7,8,2,3,1,1,1,10,11,5,6,2,4,7,8,5,6};

        Solution solution = new Solution();
        //solution.insertSort(ints);
        //solution.quickSort(0, ints.length - 1, ints);
        System.out.println(solution.findKthLargest(ints, 2));
        System.out.println(Arrays.asList(ints));

    }

    public int findKthLargest(int[] nums, int k) {
        if(nums.length == 0) {
            return 0;
        }

        quickSort3(0, nums.length - 1, nums);
        //quickSort(nums, 0, nums.length - 1);
        //selectSort(nums);

        return nums[nums.length - k];
    }

    /**
     * 选择排序
     * 基本思想：
     * 在要排序的一组数中，选出最小（或者最大）的一个数与第 1 个位置的数交换；
     * 然后在剩下的数当中再找最小（或者最大）的与第 2 个位置的数交换，依次类推，
     * 直到第 n-1 个元素（倒数第二个数）和第 n个 元素（最后一个数）比较为止。
     *
     * 3, 2, 1, 5, 6, 4
     *
     * @param arr
     */
    public void selectSort(int[] arr) {

        int temp = 0;

        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }

        System.out.println(arr);
    }

    /**
     * 插入排序
     * 基本思想:
     * 将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增 1 的有序表。
     * 即：先将序列的第 1 个记录看成是一个有序的子序列，然后从第 2 个记录逐个进行插入，直至整个序列有序为止。
     * 要点：设立哨兵，作为临时存储和判断数组边界之用。
     *
     * 时间复杂度 O(n^2)
     *
     * @param a
     */
    public void insertSort(int[] a) {

        for (int i = 0; i < a.length; i++) {
            int temp = a[i];
            int j = i;
            for (; j > 0 && a[j - 1] > temp; j--) {
                a[j] = a[j-1];
            }
            a[j] = temp;
        }

        System.out.println(a);

    }

    /**
     * 快速排序
     * 时间复杂度 O(nlog2n)
     *
     * @param left
     * @param right
     * @param arr
     */
    public void quickSort(int left, int right, int[] arr) {

        // 递归终止条件
        if (left >= right) {
            return;
        }

        int l = left;
        int r = right;
        int flag = left;
        int temp = 0;

        while (left < right) {

            // 从右开始遍历
            while (left < right && arr[flag] <= arr[right]) {
                right--;
            }

            if (arr[flag] > arr[right] && flag < right) {
                temp = arr[flag];
                arr[flag] = arr[right];
                arr[right] = temp;
                flag = right;
            }

            // 从左开始遍历
            while (left < right && arr[flag] >= arr[left]) {
                left++;
            }
            if (arr[flag] < arr[left] && flag > left) {
                temp = arr[flag];
                arr[flag] = arr[left];
                arr[left] = temp;
                flag = left;
            }

        }

        System.out.println(Arrays.toString(arr));
        quickSort(l, left - 1, arr);
        quickSort(left + 1, r, arr);
    }

    public void quickSort2(int left, int right, int[] arr) {
        if (left >= right) {
            return;
        }
        int l = left, r = right, flag = left, temp = 0;

        while (left < right) {
            while (left < right && arr[flag] <= arr[right]) {
                right--;
            }
            if (left < right && arr[flag] > arr[right]) {
                temp = arr[flag];
                arr[flag] = arr[right];
                arr[right] = temp;
                flag = right;
            }
            while (left < right && arr[flag] > arr[left]) {
                left++;
            }
            if (left < right && arr[flag] <= arr[left]) {
                temp = arr[flag];
                arr[flag] = arr[left];
                arr[left] = temp;
                flag = left;
            }

            System.out.println(Arrays.toString(arr));
            quickSort2(l, left - 1, arr);
            quickSort2(left + 1, r, arr);
        }
    }

    public void quickSort3(int left, int right, int[] arr) {
        if (left >= right) {
            return;
        }

        int l = left, r = right, flag = left, temp = 0;
        while (left < right) {
            while (left < right && arr[flag] <= arr[right]) {
                right--;
            }
            if (left < right && arr[flag] > arr[right]) {
                temp = arr[flag];
                arr[flag] = arr[right];
                arr[right] = temp;
                flag = right;
            }
            while (left < right && arr[flag] >= arr[left]) {
                left++;
            }
            if (left < right && arr[flag] < arr[left]) {
                temp = arr[flag];
                arr[flag] = arr[left];
                arr[left] = temp;
                flag = left;
            }

            System.out.println(Arrays.toString(arr));
            quickSort3(l, left - 1, arr);
            quickSort3(left + 1, r, arr);
        }
    }

/*    public void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int pivot = left;
            int index = left + 1;
            for (int i = index; i <= right; i++) {
                if (nums[pivot] < nums[i]) {
                    swap(nums, index, i);
                    index++;
                }
            }
            swap(nums, index - 1, pivot);
            pivot = index - 1;
            quickSort(nums, left, pivot - 1);
            quickSort(nums, pivot + 1, right);
        }
    }*/

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
